One of the main milestones in quantum information science is to realizequantum devices that exhibit an exponential computational advantage overclassical ones without being universal quantum computers, a state of affairsdubbed quantum speedup, or sometimes "quantum computational supremacy". Theknown schemes heavily rely on mathematical assumptions that are plausible butunproven, prominently results on anti-concentration of random prescriptions. Inthis work, we aim at closing the gap by proving two anti-concentrationtheorems. Compared to the few other known such results, these results give riseto comparably simple, physically meaningful and resource-economical schemesshowing a quantum speedup in one and two spatial dimensions. At the heart ofthe analysis are tools of unitary designs and random circuits that allow us toconclude that universal random circuits anti-concentrate.
展开▼
